﻿///
///  Filename:  Point.cs
///  Author:    Sérgio Severino, nº 9733
///   /*
///      Implementation:  10/06/2012
///   */
///

using System;

namespace KDTreeLib
{
    /// <summary>
    /// Classe que guarda coordenadas de k dimensões
    /// e um valor do tipo escolhido
    /// </summary>
    public class Point<T>
    {
        public readonly int[] coordinate;
        public int this[int index] { get { return coordinate[index]; } }

        public int Length { get { return coordinate.Length; } }

        private int? hash;

        public T value;

        /// <summary>
        /// Construtor principal
        /// </summary>
        /// <param name="coordinate">A coordenada</param>
        public Point(int[] coordinate)
        {
            if (coordinate == null)
                throw new ArgumentNullException("coordinate");

            this.coordinate = (int[])coordinate.Clone();
        }

        /// <summary>
        /// Segundo construtor
        /// </summary>
        /// <param name="coordinate">A coordenada</param>
        /// <param name="value">O argumento a guardar</param>
        public Point(int[] coordinate, T value)
            : this(coordinate)
        {
            this.value = value;
        }


        public override string ToString()
        {
            string str = "";

            if (this.coordinate == null)
                str += "empty";
            else
            {
                str += "[";
                for (int i = 0; i < this.coordinate.Length; i++)
                {
                    str += (i == 0 ? "" : ", ");
                    str += this.coordinate[i].ToString();
                }
                str += "]";
            }
            return str;
        }

        public override int GetHashCode()
        {
            if (hash == null)
            {
                int result = 84;
                for (int i = 0; i < this.coordinate.Length; i++)
                {
                    result = (result * 12) + this.coordinate[i];
                }
                hash = result;
            }
            return hash.GetValueOrDefault();
        }

        public override bool Equals(object obj)
        {
            return this == (obj as Point<T>);
        }

        public bool Equals(Point<T> obj)
        {
            return this == obj;
        }

        /// <summary>
        /// Comparação com o operador ==
        /// </summary>
        /// <param name="x">O primeiro ponto</param>
        /// <param name="y">O segundo ponto</param>
        /// <returns>true se são iguais</returns>
        public static bool operator ==(Point<T> x, Point<T> y)
        {
            if (ReferenceEquals(x, y))
                return true;

            if (ReferenceEquals(x, null) || ReferenceEquals(y, null))
                return false;

            if (x.hash.HasValue && y.hash.HasValue && // exploit known different hash
                x.hash.GetValueOrDefault() != y.hash.GetValueOrDefault())
                return false;

            int[] xdata = x.coordinate, ydata = y.coordinate;
            if (xdata.Length != ydata.Length)
                return false;

            for (int i = 0; i < xdata.Length; i++)
            {
                if (xdata[i] != ydata[i])
                    return false;
            }

            return true;
        }

        /// <summary>
        /// Comparação com o operador !=
        /// </summary>
        /// <param name="x">O primeiro ponto</param>
        /// <param name="y">O segundo ponto</param>
        /// <returns>true se são diferentes</returns>
        public static bool operator !=(Point<T> x, Point<T> y)
        {
            return !(x == y);
        }

        /// <summary>
        /// Metodo que devolve uma cópia do ponto
        /// </summary>
        /// <returns>Uma cópia do pontp</returns>
        public Point<T> Clone()
        {
            Point<T> p = new Point<T>((int[])this.coordinate.Clone());
            p.value = this.value;

            return p;
        }

        /// <summary>
        /// Metodo que ordena uma lista de pontos com base no eixo
        /// </summary>
        /// <param name="list">A lista de pontos</param>
        /// <param name="axis">O eixo de comparação</param>
        public static void Merge_sort(Point<T>[] list, int axis)
        {
            Point<T>.mergesort(list, axis, 0, list.Length - 1);
        }

        /// <summary>
        /// Metodo que ordena uma lista de pontos com base no eixo
        /// </summary>
        /// <param name="list">A lista de pontos</param>
        /// <param name="axis">O eixo de comparação</param>
        /// <param name="start">O primeiro elemento da lista a comparar</param>
        /// <param name="end">O último elemento da lista a comparar</param>
        private static void mergesort(Point<T>[] list, int axis, int start, int end)
        {
            // If the list has more than one member, sorts
            if (start < end)
            {
                int mid = (start + end) / 2;
                // ordena a primeira metade
                Point<T>.mergesort(list, axis, start, mid);
                // ordena a segunda metade
                Point<T>.mergesort(list, axis, mid + 1, end);
                // junta e ordena as duas metades
                Point<T>.merge(list, axis, start, mid, end);
            }
        }

        /// <summary>
        /// Metodo que ordena a lista recebida
        /// </summary>
        /// <param name="list">Uma lista de pontos</param>
        /// <param name="axis">O eixo a comparar</param>
        /// <param name="start">O inicio da lista</param>
        /// <param name="mid">O meio da lista</param>
        /// <param name="end">O final da lista</param>
        private static void merge(Point<T>[] list, int axis, int start, int mid, int end)
        {
            Point<T>[] auxList = new Point<T>[list.Length];

            for (int i = start; i <= end; i++)
            {
                auxList[i] = (Point<T>)list[i].Clone();
            }

            int subIndexLeft = start;
            int subIndexRight = mid + 1;
            int mainIndex = start;

            // ordena a lista
            while (subIndexLeft <= mid && subIndexRight <= end)
            {
                if (auxList[subIndexLeft].FirstIsSmaller(auxList[subIndexRight], axis, axis))
                {
                    list[mainIndex] = auxList[subIndexLeft];
                    subIndexLeft++;
                }
                else
                {
                    list[mainIndex] = auxList[subIndexRight];
                    subIndexRight++;
                }
                mainIndex++;
            }

            while (subIndexLeft <= mid)
            {
                list[mainIndex] = auxList[subIndexLeft];
                mainIndex++;
                subIndexLeft++;
            }

            auxList = null;
        }

        /// <summary>
        /// Metodo que compara dois eixos com base no eixo
        /// </summary>
        /// <param name="second">O segundo ponto</param>
        /// <param name="axis">O eixo</param>
        /// <returns>true se this é mais pequeno</returns>
        public bool FirstIsSmaller(Point<T> second, int axis)
        {
            return this.FirstIsSmaller(second, axis, axis);
        }

        /// <summary>
        /// Metodo que compara dois eixos com base no eixo base até ao eixo actual
        /// </summary>
        /// <param name="second">O segundo ponto</param>
        /// <param name="baseAxis">O eixo base</param>
        /// <param name="currentAxis">O eixo actual</param>
        /// <returns>true se this é mais pequeno</returns>
        private bool FirstIsSmaller(Point<T> second, int baseAxis, int currentAxis)
        {
            int index = (baseAxis == 0 ? this.Length : baseAxis) - 1;

            if (this[currentAxis] < second[currentAxis])
                return true;
            else if (this[currentAxis] == second[currentAxis] && index != currentAxis)
                // se os valores forem iguais, compara o proximo eixo
                return this.FirstIsSmaller(second, baseAxis, (currentAxis + 1) % this.Length);
            else
                return false;

        }

        /// <summary>
        /// Metodo que devolve o quadrado da distância entre dois pontos
        /// </summary>
        /// <param name="point">O segundo ponto</param>
        /// <returns>O quadrado da distância</returns>
        public ulong Distance(Point<T> point)
        {
            if (this.Length != point.Length)
                throw new ArgumentOutOfRangeException();

            ulong distance = 0;

            for (int i = 0; i < this.Length; i++)
            {
                ulong tmp = (ulong)(point[i] - this[i]);
                distance += tmp * tmp;
            }

            return distance;
        }
    }
}
